本题来自力扣35题搜索插入位置  难度：简单

反转列表

如果元素在列表中，那么直接返回位置即可很简单，如果不在，那么就用到了题目的话：搜索插入位置

首先，我想到的是遍历列表，目标元素和列表里的元素比较，如果目标元素比列表里的元素大那么就插入。

后来以失败告终，现在想想这个想法还是挺傻的，target=,5num=[2,3,4,8]，5比2，3，4都大，应该插入到比目标元素小的中的最大的一个。这么做还要额外开辟空间记录比目标元素小的元素有哪些，果断放弃。

换个思路，只要将列表反转过来，判断目标元素比列表里的元素大就行，那么第一个满足条件的就应该是正确的 num=[1,3,5,6] target=4 反转后nums=[6,5,3,1],那么 在3的前面就满足条件4>3就不会往后走了，只需要记录3的索引值+1就是应该插入的位置。如果target比列表里的任何一个元素都小，那么直接返回0就行

    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
			 for i in nums[::-1]:
                if target<nums[0]:
                    return 0
                if target>i:
                    return nums.index(i)+1

二分查找

想找到插入的位置，可以用二分查找，类似于猜商品价格。

客户：40

老板：大了

客户：20

老板：小了

客户：30

老板：没错

 def searchInsert(self, nums: List[int], target: int) -> int:


        low, high = 0, len(nums) - 1

        # 在 [low, high] 找 target
        while low <= high:

            mid = (low + high) // 2

            # 如果 target 找到，直接返回位置
            if nums[mid] == target:
                return mid
            # 如果 target 大于中间数，则 target 可能在右区间
            # 在 [mid + 1, left] 中找
            elif nums[mid] < target:
                low = mid + 1
            # 如果 target 小于中间数，则 target 可能在左区间
            # 在 [left, mid -1] 中找
            else:
                high = mid - 1
        
        # 如果在数组中没找到，则返回需要插入数值的位置
        return high + 1

一直循环直到左边界大于右边界，将target值与中间数做比较，大了它就在中间数右边界，同时重置区间，左边界应该从0中间数右边那个开始，再次判断新的区间的中间数与目标值的大小关系，以此类推直到找到目标数为止。

如果目标值小于列表里的任何一个数，那么右边界(high值）就会一直减小直到它和左边界相等为止，此时它们都为0，然后再次进入 

  else:
       	high = mid - 1

这句判断，high被减小为-1，返回的时候将high+1就是0了

同理，如果target比列表里任何一个值都大，那么左边界（low值）就会不断增加，直到与high相等都为len(nums)-1为止，此时最后一遍循环进入

elif nums[mid] < target:
       low = mid + 1            

high一直没变为原列表最后一个数字的索引，现在在最右边插入一个target那么它的索引自然就是high+1了